package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-02-23 20:49
 */

class ResultType {
    int minSub;
    TreeNode minSubNode;
    int sum;

    public ResultType(int minSub, TreeNode minSubNode, int sum) {
        this.minSub = minSub;
        this.minSubNode = minSubNode;
        this.sum = sum;
    }
}

public class QLint596II {
    public TreeNode findSubtree(TreeNode root) {
        ResultType result = helper(root);
        return result.minSubNode;
    }

    private ResultType helper(TreeNode root) {
        if (root == null) {
            return new ResultType(Integer.MAX_VALUE, null, 0);
        }

        ResultType left = helper(root.left);
        ResultType right = helper(root.right);

        int sum = left.sum + right.sum + root.val;

        if(left.minSub == Math.min(sum, Math.min(left.minSub, right.minSub))) {
            return new ResultType(left.minSub, left.minSubNode, sum);
        }

        if(right.minSub == Math.min(sum, Math.min(left.minSub, right.minSub))) {
            return new ResultType(right.minSub, right.minSubNode, sum);
        }

        return new ResultType(sum, root, sum);
    }

}
